/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/merge-k-sorted-interval-lists
   @Language: C++
   @Datetime: 19-04-28 15:56
   */

/**
 * Definition of Interval:
 * classs Interval {
 *     int start, end;
 *     Interval(int start, int end) {
 *         this->start = start;
 *         this->end = end;
 *     }
 * }
 */


// Method 1, using MergeTwoIntervals, Time 202ms
class Solution {
	void merge(vector<Interval> &vi, Interval &a){
		if(vi.size() && vi.back().end>=a.start)
			vi.back().end=max(vi.back().end,a.end);
		else vi.push_back(a);
	}
	vector<Interval> mergeTwoInterval(vector<Interval> &list1, vector<Interval> &list2) {
		// write your code here
		if(list1.size()==0) return list2;
		if(list2.size()==0) return list1;
		vector<Interval> vi;
		for(int i=0, j=0; i<list1.size() || j<list2.size();){
			if(i>=list1.size() || list1[i].start>list2[j].start)
				merge(vi,list2[j++]);
			else if(j>=list1.size() || list1[i].start<list2[j].start)
				merge(vi,list1[i++]);
			else {
				Interval tmp(list1[i].start, max(list1[i].end,list2[j].end));
				++i, ++j;
				merge(vi,tmp);
			}
		}
		return vi;
	}
public:
	/**
	 * @param intervals: the given k sorted interval lists
	 * @return:  the new sorted interval list
	 */
	vector<Interval> mergeKSortedIntervalLists(vector<vector<Interval> > &intervals) {
		// write your code here
		if(intervals.size()<1) return {};
		for(int i=0, j=intervals.size()-1; j; ++i){
			i=i>=j?0:i;
			intervals[i]=mergeTwoInterval(intervals[i],intervals[j--]);
		}
		return intervals[0];
	}
};


// Method 2, MiniHeap, Time 385ms
class Solution {
	struct Node{
		Interval value;
		int array, index;
		Node(Interval &val, int arr, int idx):value(val),array(arr),index(idx){}
		bool operator<(const Node &a)const{
			return value.start > a.value.start; // mini heap
		}
	};
public:
	/**
	 * @param intervals: the given k sorted interval lists
	 * @return:  the new sorted interval list
	 */
	vector<Interval> mergeKSortedIntervalLists(vector<vector<Interval> > &intervals) {
		// write your code here
		priority_queue<Node> heap;  // mini heap
		vector<Interval> res;
		for(int i=0; i<intervals.size(); ++i)
			if(intervals[i].size()) heap.push(Node(intervals[i][0],i,1));
		for(; heap.size(); heap.pop()){
			const Node &n=heap.top();
			if(res.size()==0 || res.back().end<n.value.start) res.push_back(n.value);
			else res.back().end=max(res.back().end,n.value.end);
			if(n.index<intervals[n.array].size())
				heap.push(Node(intervals[n.array][n.index],n.array,n.index+1));
		}
		return res;
	}
};

